package com.lordjoe.collectiveintelligence;

import java.util.*;

/**
 * com.lordjoe.collectiveintelligence.OptimizationUtilities
 *
 * @author Steve Lewis
 * @date Mar 24, 2009
 */
public class OptimizationUtilities
{
    public static OptimizationUtilities[] EMPTY_ARRAY = {};
    public static Class THIS_CLASS = OptimizationUtilities.class;
    public static final Random RND = new Random();

    public static final int NUMBER_START_STEPS = 50;
    public static final int MAX_NO_MOVE_STEPS = 50;

    protected static FlightItinery findStartPoint(FlightOptimization problem,
                                                  ICostFunction<FlightItinery> cost)
    {
        double bestCost = Double.MAX_VALUE;
        FlightItinery best = null;
        for (int i = 0; i < NUMBER_START_STEPS; i++) {
            FlightItinery test = problem.randomItinery(cost);
            double testCost = test.getCost();
            if (testCost < bestCost) {
                best = test;
                bestCost = testCost;
            }
        }
        return best;
    }


    public static FlightItinery randomSearch(FlightOptimization problem,
                                             ICostFunction<FlightItinery> cost)
    {
        FlightItinery best = findStartPoint(problem, cost);
        return randomSearchFrom(problem, cost, best);
    }

    public static FlightItinery hillClimb(FlightOptimization problem,
                                          ICostFunction<FlightItinery> cost)
    {
        FlightItinery best = findStartPoint(problem, cost);
        return hillClimbFrom(problem, cost, best);
    }

    public static FlightItinery hillClimbFrom(FlightOptimization problem,
                                              ICostFunction<FlightItinery> cost,
                                              FlightItinery start)
    {
        int step = 0;
        int numbernoMoveSteps = 0;
        double bestCost = start.getCost();
        FlightItinery best = start;
        while (numbernoMoveSteps < MAX_NO_MOVE_STEPS) {
            step++;
            FlightItinery[] tests = best.getCloseItineries();
            for (int i = 0; i < tests.length; i++) {
                FlightItinery test = tests[i];
                double testCost = test.getCost();
                if (testCost < bestCost) {
                    best = test;
                    bestCost = testCost;
                    numbernoMoveSteps = 0;
                    if(step % 20 == 0)
                       System.out.println("Step " + step + " cost " + (int)bestCost);
                }
            }
            numbernoMoveSteps++;
        }
        System.out.println("=============== Hill Climb ==================================");
        System.out.println("Done after " + step + " cost " + (int) bestCost);
        return best;
    }

    public static FlightItinery randomSearchFrom(FlightOptimization problem,
                                                 ICostFunction<FlightItinery> cost,
                                                 FlightItinery start)
    {
        int step = 0;
        int numbernoMoveSteps = 0;
        double bestCost = start.getCost();
        FlightItinery best = start;
        while (numbernoMoveSteps < MAX_NO_MOVE_STEPS) {
            step++;
            FlightItinery test = best.getCloseItinery();
            double testCost = test.getCost();
            if (testCost < bestCost) {
                best = test;
                bestCost = testCost;
                numbernoMoveSteps = 0;
                if(step % 20 == 0)
                    System.out.println("Step " + step + " cost " + (int)bestCost);
            }
            else {
                numbernoMoveSteps++;
            }
        }
        System.out.println("================= Random Search ================================");
        System.out.println("Done after " + step + " cost " + (int) bestCost);
        return best;
    }

    public static FlightItinery simulatedAnnealing(FlightOptimization problem,
                                                   ICostFunction<FlightItinery> cost)
    {
        FlightItinery best = findStartPoint(problem, cost);
        return simulatedAnnealingFrom(problem, cost, best);
    }

    public static FlightItinery simulatedAnnealingFrom(FlightOptimization problem,
                                                       ICostFunction<FlightItinery> cost,
                                                       FlightItinery start)
    {
        double temperature = 1;
        int step = 0;
        int numbernoMoveSteps = 0;
        double bestCost = start.getCost();
        FlightItinery best = start;
        while (numbernoMoveSteps < MAX_NO_MOVE_STEPS) {
            step++;
            double bestTestScore = Double.MAX_VALUE;
            FlightItinery bestThisRound = null;
            FlightItinery[] tests = best.getCloseItineries();
            for (int i = 0; i < tests.length; i++) {
                FlightItinery test = tests[i];
                double testCost = test.getCost();
                if (testCost < bestTestScore) {
                    bestThisRound = test;
                    bestTestScore = testCost;
                }
                if (testCost < bestCost) {
                    best = test;
                    bestCost = testCost;
                    numbernoMoveSteps = 0;
                    if(step % 20 == 0)
                         System.out.println("Step " + step + " cost " + (int)bestCost);
                }
                if (RND.nextDouble() < temperature) {
                    best = bestThisRound;
                    bestCost = bestTestScore;
                    numbernoMoveSteps = 0;
                }
            }
            numbernoMoveSteps++;
            temperature *= 0.99;
        }
        System.out.println("=============== Simulated Annealing ==================================");
        System.out.println("Done after " + step + " cost " + (int) bestCost);
        return best;
    }


    public static final int NUMBER_WINNERS = 16;
    public static final int NUMBER__SAVED_WINNERS = 4;
    public static final double MUTATION_PROBABILITY = 0.5;

    public static FlightItinery geneticEvolution(FlightOptimization problem,
                                                 ICostFunction<FlightItinery> cost)
    {
        FlightItinery[] items = new FlightItinery[NUMBER_WINNERS];
        for (int i = 0; i < items.length; i++) {
            items[i] = problem.randomItinery(cost);
        }
        return geneticEvolutionFrom(problem, cost, items);
    }

    /**
     * find lowest cost Itinery
     * @param items  array to test
     * @return  non-null items
     */
    public static FlightItinery getLowestCost(FlightItinery[] items)
    {
        FlightItinery[] copy = items.clone();
        Arrays.sort(copy, CostSort.INSTANCE);
        return items[0];
    }

    public static FlightItinery geneticEvolutionFrom(FlightOptimization problem,
                                                     ICostFunction<FlightItinery> cost,
                                                     FlightItinery[] items)
    {
        double temperature = 1;
        int step = 0;
        int numbernoMoveSteps = 0;
        FlightItinery best = getLowestCost(items);
        double bestCost = best.getCost();
        while (numbernoMoveSteps < 10 * MAX_NO_MOVE_STEPS) {
            step++;
            boolean combine = RND.nextDouble() < MUTATION_PROBABILITY;
            if (combine) {
                items = combineWinners(items);
            }
            else {
                items = searchWinners(items);

            }
            FlightItinery test = getLowestCost(items);

            // find the best
            if (test.getCost() < bestCost) {
                best = test;
                bestCost = test.getCost();
                numbernoMoveSteps = 0;
                System.out.println("genetic  after " + step + " cost " + (int)bestCost);
            }
            numbernoMoveSteps++;
        }
        System.out.println("========== Genetic =======================================");
        System.out.println("Done after " + step + " cost " + (int)bestCost);
        return best;
    }

    protected static FlightItinery[] getWinners(FlightItinery[] items)
    {
        FlightItinery[] saved = new FlightItinery[NUMBER__SAVED_WINNERS];
        Arrays.sort(items, CostSort.INSTANCE);
        for (int i = 0; i < saved.length; i++) {
            saved[i] = items[i];
        }
        return saved;
    }

    protected static FlightItinery[] searchWinners(FlightItinery[] items)
    {
        FlightItinery[] winners = getWinners(items);
        FlightItinery[] ret = new FlightItinery[items.length];
        int i = 0;
        // keep the winners
        for (; i < winners.length; i++) {
            ret[i] = winners[i];
        }

        // randomly add others
        for (; i < ret.length; i++) {
            FlightItinery alter = winners[RND.nextInt(winners.length)];
            ret[i] = alter.getCloseItinery();
        }
        return ret;
    }

    protected static FlightItinery[] combineWinners(FlightItinery[] items)
    {
        // choose winners
        FlightItinery[] winners = getWinners(items);

        FlightItinery[] ret = new FlightItinery[items.length];
        int i = 0;
        // copy the winners
        for (; i < winners.length; i++) {
            ret[i] = winners[i];
        }
        // combine the others
        for (; i < ret.length; i++) {
            ret[i] = geneticallyCombine(winners);
        }
        return ret;

    }

     /**
     * do a gentiuc combination of the two flight tests
     *
     * @param f1 non-null flight test
     * @param f2 non-null flight test
     * @return non-null flight test
     */
    protected  static FlightItinery  geneticallyCombine(FlightItinery[] items)
     {
         FlightItinery f1 = items[RND.nextInt(items.length)];
         FlightItinery f2 = items[RND.nextInt(items.length)];
         while(f1 == f2)
            f2 = items[RND.nextInt(items.length)];
         return geneticallyCombine(f1,f2);
     }

    /**
     * do a gentiuc combination of the two flight tests
     *
     * @param f1 non-null flight test
     * @param f2 non-null flight test
     * @return non-null flight test
     */
    protected  static FlightItinery geneticallyCombine(FlightItinery f1, FlightItinery f2)
    {
        ItineryItem[] items1 = f1.getItems();
        ItineryItem[] items2 = f2.getItems();
        int cut1 = 1 + RND.nextInt(items1.length - 2);
        int cut2 = 1 + RND.nextInt(items1.length - 2);
        ItineryItem[] result = new ItineryItem[items1.length];
        for (int i = 0; i < result.length; i++) {
            String person = items1[i].getPerson();
            Flight arrive = null;
            Flight depart = null;
            // combine arrival
            if(i < cut1)
                   arrive = items1[i].getArrival();
              else
                  arrive = items2[i].getArrival();

            // combine return
            if(i < cut2)
                   depart = items1[i].getReturn();
              else
                  depart = items2[i].getReturn();

            result[i] = new ItineryItem(person,arrive,depart);

        }
        return new FlightItinery(result, f1.getProblem(), f1.getCostFunction());
    }
    /**
     * first cut at combination of the two flight tests
     *
     * @param f1 non-null flight test
     * @param f2 non-null flight test
     * @return non-null flight test
     */
    protected  static FlightItinery geneticallyCombine1(FlightItinery f1, FlightItinery f2)
    {
        ItineryItem[] items1 = f1.getItems();
        ItineryItem[] items2 = f2.getItems();
        int cut = 1 + RND.nextInt(items1.length - 2);
        ItineryItem[] result = new ItineryItem[items1.length];

        for (int i = 0; i < cut; i++) {
            result[i] = items1[i];

        }
        for (int i = cut; i < items1.length; i++) {
            result[i] = items2[i];
        }
        return new FlightItinery(result, f1.getProblem(), f1.getCostFunction());
    }


    public static int parseTime(String s)
    {
        String[] items = s.split(":");
        return 60 * Integer.parseInt(items[0]) + Integer.parseInt(items[1]);
    }


    public static String stringTime(int s)
    {
        StringBuilder sb = new StringBuilder();
        sb.append(Integer.toString(s / 60));
        sb.append(":");
        int i = s % 60;
        String str = Integer.toString(i);
        while(str.length() < 2)
            str = "0" + str;
        sb.append(str);
        return sb.toString();
    }

    public static int arrivalWait(ItineryItem target, ItineryItem[] allFlights)
    {
        int ret = 0;
        int start = target.getArrival().getArriveTime();
        for (int i = 0; i < allFlights.length; i++) {
            ItineryItem flt = allFlights[i];
            int test = flt.getArrival().getArriveTime();
            ret = Math.max(ret, test - start);
        }
        return ret;
    }


    public static int departWait(ItineryItem target, ItineryItem[] allFlights)
    {
        int ret = 0;
        int end = target.getReturn().getStartTime();
        for (int i = 0; i < allFlights.length; i++) {
            ItineryItem flt = allFlights[i];
            int test = flt.getReturn().getStartTime();
            ret = Math.max(ret, end - test);
        }
        return ret;
    }
}
